package com.skh.binaryTree;

/**
 * 二叉树的直径
 * created by skh on 2020/3/7
 */
public class DiameterOfBinaryTree {

	/**
	 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
	 *
	 * 示例 :
	 * 给定二叉树
	 *
	 *           1
	 *          / \
	 *         2   3
	 *        / \
	 *       4   5
	 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
	 *
	 * 注意：两结点之间的路径长度是以它们之间边的数目表示。
	 */

	int max = 0;
	public int diameterOfBinaryTree(TreeNode root) {
		depth(root);

		return max;
	}

	public int depth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int lDepth = depth(root.left); //找出左子树最大深度
		int rDepth = depth(root.right); //找出右子树最大深度
		max = Math.max(lDepth + rDepth, max); //当前节点作为父节点的左右子树中各自的最大高度相加和全局max比较
		return Math.max(lDepth,rDepth)+1; //返回当前节点的最大高度
	}
}
